// 46. [DFS递归不重复数字] 全排列
// https://leetcode.cn/problems/permutations/
// https://blog.csdn.net/qq_33185750/article/details/108093916
// https://www.cnblogs.com/grandyang/p/4358848.html
//给定一个不含重复数字的数组 nums [-10,10]返回其 所有可能的全排列 。你可以
//按任意顺序 返回答案。 输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//输入：nums = [0,1]
//输出：[[0,1],[1,0]]
//输入：nums = [1]
//输出：[[1]]
#include <bits/stdc++.h>
using namespace std;
#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif
class Solution {
  vector<vector<int>> res_;
  vector<int> nums_;
  vector<int> vtVisited_;
  void dfs(int depth) {
    if (depth == nums_.size()) {
      res_.push_back(nums_);
      return;
    }
    for (size_t i = depth; i < nums_.size(); i++) {
      swap(nums_[i], nums_[depth]);
      dfs(depth + 1);
      swap(nums_[i], nums_[depth]);
    }
  }

 public:
  vector<vector<int>> permute(vector<int> nums) {
    nums_ = nums;
    vtVisited_.resize(nums.size());
    std::sort(nums_.begin(), nums_.end());
    dfs(0);
    return res_;
  }
};
int main() {
  Solution sol;
  vector<vector<int>> out = sol.permute({1, 2, 3});
  for (auto vt : out) {
    for (auto n : vt) {
      PF("%d,", n);
    }
    PF("\n");
  }
  return 0;
}